package main

import "fmt"

func countingSort(arr []int) []int {
	// Find the maximum element in the array
	max := arr[0]
	for i := 1; i < len(arr); i++ {
		if arr[i] > max {
			max = arr[i]
		}
	}

	// Create a count array to store the count of each element
	count := make([]int, max+1)
	for i := 0; i < len(arr); i++ {
		count[arr[i]]++
	}

	// Modify the count array to store the actual position of each element in the output array
	for i := 1; i <= max; i++ {
		count[i] += count[i-1]
	}

	// Create the output array
	output := make([]int, len(arr))

	// Place each element in its correct position in the output array
	for i := len(arr) - 1; i >= 0; i-- {
		output[count[arr[i]]-1] = arr[i]
		count[arr[i]]--
	}

	return output
}

func CountingSortTest() {
	arr := []int{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}
	fmt.Print("Unsorted Array: ", arr)
	sortedArr := countingSort(arr)
	fmt.Println("Sorted Array: ", sortedArr)
}
